//https://leetcode.cn/problems/accounts-merge/submissions/582327925/

class Solution {
    vector<int> parent; // 并查集数组，记录每个邮箱对应的父节点索引

    // 并查集查找函数，路径压缩优化
    int find(int x){
        if(parent[x] != x)
            parent[x] = find(parent[x]); // 路径压缩
        return parent[x];
    }
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        map<string, int> emailToIndex; // 邮箱到索引的映射
        map<string, string> emailToName; // 邮箱到用户名的映射
        int emailCount = 0; // 邮箱计数器

        // 第一次遍历，给每个邮箱分配唯一的索引，并记录邮箱对应的用户名
        for(auto& account : accounts){
            string& name = account[0]; // 用户名
            int size = account.size();
            for(int i = 1; i < size; ++i){
                string& email = account[i];
                if(!emailToIndex.count(email)){
                    emailToIndex[email] = emailCount++; // 分配索引
                    emailToName[email] = name; // 记录用户名
                }
            }
        }

        // 初始化并查集，每个邮箱的父节点初始为自己
        parent.resize(emailCount);
        for(int i = 0; i < emailCount; ++i){
            parent[i] = i;
        }

        // 第二次遍历，合并同一账户下的所有邮箱
        for(auto& account : accounts){
            int size = account.size();
            string& firstEmail = account[1];
            int firstIndex = emailToIndex[firstEmail];
            for(int i = 2; i < size; ++i){
                string& nextEmail = account[i];
                int nextIndex = emailToIndex[nextEmail];
                // 合并两个邮箱的父节点
                parent[find(nextIndex)] = find(firstIndex);
            }
        }

        // 将同一父节点下的邮箱合并到一起
        map<int, vector<string>> indexToEmails; // 父节点索引到邮箱列表的映射
        for(auto& [email, idx] : emailToIndex){
            int rootIndex = find(idx); // 找到邮箱的根节点
            indexToEmails[rootIndex].push_back(email); // 添加到对应的邮箱列表中
        }

        // 构造结果
        vector<vector<string>> merged;
        for(auto& [rootIdx, emails] : indexToEmails){
            sort(emails.begin(), emails.end()); // 邮箱排序
            string& name = emailToName[emails[0]]; // 获取用户名
            vector<string> account;
            account.emplace_back(name); // 添加用户名
            account.insert(account.end(), emails.begin(), emails.end()); // 添加邮箱列表
            merged.emplace_back(account); // 添加到结果集
        }
        return merged;
    }
};
